package com.njupt.huawei;

import java.util.*;


/**
 * @Author: wujiaming
 * @CreateTime: 2025/4/22 21:00
 * @Description: 地铁耗时最短的路线
 * 本质式Dijkstra算法
 * 1、邻接表的图的保存
 * 2、minDest每个节点到起始点的最短路径
 * 3、路径的保存，当前节点的前一个最短路径的保存
 * @Version: 1.0
 *
 * 12
 * a e
 * a b 2
 * b c 2
 * c d 2
 * d e 2
 * f b 3
 * b g 3
 * g h 2
 * h i 3
 * j h 2
 * h e 3
 * e k 2
 * k l 4
 * 0000
 */


public class MetroRoutePlanner2 {

    static class Node{
        Character station;
        int distance;
        
        public Node(Character station,int distance){
            this.station = station;
            this.distance = distance;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());

        String[] s = sc.nextLine().split(" ");
        Character start = s[0].charAt(0);
        Character end = s[1].charAt(0);

        //定义,并且构建邻接表
        Map<Character, Map<Character,Integer>> graph = new HashMap<>();
        Map<Character,Boolean> isVisited = new HashMap<>();


        //1、构造邻接表
        while (true) {
            String line = sc.nextLine();
            if ("0000".equals(line)){
                break;
            }
            String[] parts = line.split(" ");
            Character from = parts[0].charAt(0);
            Character to = parts[1].charAt(0);
            int distance = Integer.parseInt(parts[2]);
            //保存一个节点的出边以及边对应的权值
            graph.putIfAbsent(from,new HashMap<Character,Integer>());  //可以理解成初始化邻接表
            isVisited.putIfAbsent(from,Boolean.FALSE);                 //判断当前节点有没有被访问过
            graph.get(from).put(to,distance);                          //记录from->to的边，并且记录权值
            
            graph.putIfAbsent(to,new HashMap<Character,Integer>());
            isVisited.putIfAbsent(to,Boolean.FALSE);
            graph.get(to).put(from,distance);                          //记录to->from的边，并且记录权值
            
        }

        Map<Character,Integer> minDist = new HashMap<>();              //hashmap 记录源点到所有节点的最短路径，初始化为无穷大，只有源点到源点的最小距离为零
        Map<Character,Character> parent = new HashMap<>();             //hashmap 记录当前最短路径上当前节点的前驱节点，以便打印出最短路径
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.distance));   //优先级队列记录minDist数组中最小值

        //初始化minDist数组，以及优先级队列
        for(Character station : graph.keySet()){
            if(station == start){
                minDist.put(station,0);
                pq.add(new Node(station,0));
            }else {
                minDist.put(station,Integer.MAX_VALUE);
            }
        }

        //参数：1、邻接表 2、终点 3、visited数组标识是否被遍历过 4、parent数组，最短路径上当前节点的前驱节点 5、minDist数组 6、优先级队列
        dijkstra(graph,end,isVisited,parent,minDist,pq);

        List<Character> path = new ArrayList<>();

        Character current = end;
        while(current != start){
            path.add(current);
            current = parent.get(current);
        }
        path.add(current);
        Collections.reverse(path);

        for(int i = 0 ;i < path.size() -1;i++){
            System.out.print(path.get(i) + " ");
        }
        System.out.println(path.get(path.size() - 1));
    }

    private static void dijkstra(Map<Character, Map<Character, Integer>> graph, Character end, Map<Character, Boolean> isVisited, Map<Character, Character> parent, Map<Character, Integer> minDist, PriorityQueue<Node> pq) {
    
        while(!pq.isEmpty()){
            //在minDist数组中寻找寻找最小值，这个最小值就是下一个最短路径上的节点cur，这里是从优先级队列中查找的
            Node node = pq.poll();
            Character curStation = node.station;
            if(isVisited.get(curStation)){
                continue;
            }

            //把这个节点标记为已经访问过
            isVisited.put(curStation,Boolean.TRUE);

            //跟新minDist数组，源点经过当前节点cur可达哪些邻接点
            //遍历当前离源点距离最近的节点的邻接节点
            for(Map.Entry<Character,Integer> neighbour : graph.get(curStation).entrySet()){
                Character neighbourStation = neighbour.getKey();
                if(!isVisited.get(neighbourStation)){
                    int newDistance = minDist.get(curStation) + neighbour.getValue();
                    if(newDistance < minDist.get(neighbourStation)){
                        minDist.put(neighbourStation,newDistance);
                        parent.put(neighbourStation,curStation);
                        pq.add(new Node(neighbourStation,newDistance));
                    }
                }


            }
        }
    
    }
}
